var array = [8, 3, 5, 7, 2, 4, 6, 1]

/**
 * 获得一个新数组用来排序
 * @param {*} array 待复制数组
 * @returns 深度克隆数组
 */
function deepClone(array) {
    let arr = []
    for (var i in array) {
        arr[i] = array[i]
    }
    return arr
}
/**
 * 冒泡排序
 */
function bubbleSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('冒泡排序:开始：' + arr)
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                arr[j] += arr[j + 1]
                arr[j + 1] = arr[j] - arr[j + 1]
                arr[j] -= arr[j + 1]
            }
        }
        console.log('冒泡排序：第' + (i + 1) + '趟---' + arr)
    }
}
// bubbleSort()

/**
 * 选择排序
 */
function selectionSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('选择排序:开始：' + arr)
    let minIndex, temp
    for (var i = 0; i < arr.length - 1; i++) {
        minIndex = i
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
        console.log('选择排序' + (i + 1) + '趟---' + arr)
    }
}
// selectionSort()

/**
 * 插入排序
 */
function insertSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('插入排序:开始：' + arr)
    let cur, temp
    for (var i = 1; i < arr.length; i++) {
        cur = i
        for (var j = i - 1; j >= 0; j--) {
            if (arr[j] > arr[cur]) {
                temp = arr[cur]
                arr[cur] = arr[j]
                arr[j] = temp
                cur = j
            } else {
                break
            }
        }
        console.log('插入排序' + (i) + '趟---' + arr)
    }
}
// insertSort()
/**
 * 希尔排序
 */
function shellSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('希尔排序:开始：' + arr)
    let cur, temp, gap = 1
    while (gap < array.length / 3) {
        gap = gap * 3 + 1
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        console.log('希尔排序：------gap：' + gap + '-----')
        for (var i = gap; i < arr.length; i++) {
            cur = i
            for (var j = i - gap; j >= 0 && arr[j] > arr[cur]; j -= gap) {
                temp = arr[cur]
                arr[cur] = arr[j]
                arr[j] = temp
                cur = j
                console.log('希尔排序' + (i) + '趟---' + arr)
            }
        }
    }
}
// shellSort()
/**
 * 归并排序，核心思想：分治
 */
function mergeSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('归并排序:开始：' + arr)

    function merge(left, mid, right) {
        let lStart = left
        let rStart = mid + 1
        let cur = left
        while (lStart < mid + 1) {
            if (rStart > right) {
                while (lStart < mid + 1) {
                    temp[cur++] = arr[lStart++]
                }
                break
            }
            if (arr[lStart] > arr[rStart]) {
                temp[cur] = arr[rStart]
                rStart++
            } else {
                temp[cur] = arr[lStart]
                lStart++
            }
            cur++
        }
        console.log('----归并排序 merge(' + left + '-' + right + ')----')
        console.log('temp:' + temp)
        while (left < cur) {
            arr[left] = temp[left]
            left++
        }
        console.log('arr :' + arr)
    }

    function sort(left, right) {
        console.log('----归并排序 sort(' + left + '-' + right + ')----')
        let mid = Math.floor((left + right) / 2)
        if (left !== mid) {
            sort(left, mid)
            sort(mid + 1, right)
        }
        merge(left, mid, right)
        return
    }
    let len = array.length
    let temp = new Array(len)
    sort(0, len - 1)
}
// mergeSort()

/**
 * 快速排序
 */
function quickSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('快速排序:开始：' + arr)

    function partition(left, right) {
        if (left >= right) {
            return
        }
        console.log('---- partition(' + left + '-' + right + ')----')
        let mid = sort(left, right)
        console.log('return mid:' + mid)
        console.log('arr :' + arr)
        partition(left, mid - 1)
        partition(mid + 1, right)
    }

    function sort(left, right) {
        let base = arr[left]
        let lP = left
        for (let i = left + 1; i <= right; i++) {
            console.log(i + 'sort 判断 基准值：' + base + ' > ' + arr[i] + ':' + (base > arr[i]))
            if (base > arr[i]) {
                arr[lP] = arr[i]
                lP++
                arr[i] = arr[lP]
            }
        }
        arr[lP] = base
        return lP
    }
    partition(0, array.length - 1)
    console.log('快速排序:结束：' + arr)
}
// quickSort()
/**
 * 堆排序
 */
function heapSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('堆排序:开始：' + arr)
    /**
     * 堆化
     */
    function heapify(len) {
        for (let i = Math.floor(len / 2); i >= 1; i--) {
            let parent = i
            let lagerChild = 2 * parent
            while (lagerChild <= len) {
                if (lagerChild < len && arr[lagerChild - 1] < arr[lagerChild]) {
                    lagerChild++
                }
                if (arr[lagerChild - 1] > arr[parent - 1]) {
                    swap(lagerChild - 1, parent - 1)
                    parent = lagerChild
                    lagerChild = 2 * parent
                } else {
                    break
                }
            }
        }
        console.log('长度为：' + len + ',数组堆化')
        console.log('arr：' + arr)
    }

    /**
     * 交换节点值
     */
    function swap(i1, i2) {
        let temp = arr[i1]
        arr[i1] = arr[i2]
        arr[i2] = temp
    }

    function heapSort() {
        while (len > 1) {
            heapify(len)
            swap(0, --len)
            console.log('调整:' + arr)
        }
    }
    let len = arr.length
    heapSort()
    console.log('堆排序:结束：' + arr)
}
// heapSort()
/**
 * 计数排序
 */
function countingSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('计数排序:开始：' + arr)
    let MAX = 0
    for (let i in arr) {
        MAX = Math.max(arr[i], MAX)
    }
    console.log('MAX：' + MAX)
    let countArr = new Array(MAX + 1).fill(0)
    for (let i in arr) {
        countArr[arr[i]]++
    }
    let index = 0
    for (let i in countArr) {
        while (countArr[i] > 0) {
            arr[index++] = i
            countArr[i]--
        }
    }
    console.log('计数排序:结束：' + arr)
}
// countingSort()

/**
 * 桶排序
 */
function bucketSort() {
    let arr = deepClone(array)
    console.log('--------------------')
    console.log('桶排序:开始：' + arr)
    /**
     * 插入排序
     */
    function insertSort(arr) {
        let cur, temp
        for (var i = 1; i < arr.length; i++) {
            cur = i
            for (var j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[cur]) {
                    temp = arr[cur]
                    arr[cur] = arr[j]
                    arr[j] = temp
                    cur = j
                } else {
                    break
                }
            }
        }
    }
    let MAX = 0
    let MIN = 0
    for (let i in arr) {
        MAX = Math.max(arr[i], MAX)
        MIN = Math.min(arr[i], MAX)
    }
    console.log('(MAX,MIN)' + MAX + ',' + MIN)
    const DEF_SIZE = 4
    let bucketCunt = Math.floor((MAX - MIN) / DEF_SIZE) + 1
    console.log('bucketCunt:' + bucketCunt)
    let bucket = new Array(bucketCunt)
    for (let i = 0; i < bucket.length; i++) {
        bucket[i] = []
    }
    for (let i in arr) {
        let index = Math.floor((arr[i] - MIN) / DEF_SIZE)
        console.log('映射：' + arr[i] + '->' + index)
        bucket[index].push(arr[i]);
    }
    let result = []
    for (let i in bucket) {
        insertSort(bucket[i])
        for (let j in bucket[i]) {
            result.push(bucket[i][j])
        }
    }
    console.log('桶排序:结束：' + result)
}
// bucketSort()
/**
 * 基数排序
 */
function radixSort() {
    let arr = deepClone(array)
    // let arr = [8, 3, 5, 7, 2, 4, 6, 1]
    console.log('--------------------')
    console.log('基数排序:开始：' + arr)
    let bucket = new Array(10)
    for (let i = 0; i < bucket.length; i++) {
        bucket[i] = []
    }
    let MAX = 0
    for (let i in arr) {
        MAX = Math.max(arr[i], MAX)
    }
    // 最大位数
    let maxDigit = 0
    while (MAX > 0) {
        MAX = Math.floor(MAX / 10)
        maxDigit++
    }
    console.log('maxDigit：' + maxDigit)
    let mod = 10
    let dev = 1
    for (let i = 0; i < maxDigit; i++, mod *= 10, dev *= 10) {
        for (let a in arr) {
            let bucketIndex = Math.floor((arr[a] % mod) / dev)
            console.log('bucketIndex:' + maxDigit)
            bucket[bucketIndex].push(arr[a])
        }
        let arrIndex = 0
        for (let x in bucket) {
            for (let y in bucket[x]) {
                arr[arrIndex++] = bucket[x][y]
            }
        }
    }
    console.log('基数排序:结束：' + arr)
}
radixSort()